package leetcode;

/***
 * 142
 * 快慢指针相遇的节点。   p指针和s指针必定相遇，相遇的节点就是环的入口处
 */
public class LinkedListCycle2_142 {
    class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
            next = null;
        }
    }
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null){return null;}
        ListNode fast = head,slow = head,p = head;
        while (fast !=null && fast.next != null && slow != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                while(p != slow) {
                    p = p.next;
                    slow = slow.next;
                }
                return p;
            }
        }
        return null;
    }
}
